/**
 * 69. x 的平方根
 * 给你一个非负整数 x ，计算并返回x的 算术平方根 。
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 * 思路 ： 二分法 查找 注意类型越界
 * m*m = x   x/m = m
 */
pub fn my_sqrt(x: i32) -> i32 {
    if x == 0 || x == 1 {
        return x;
    }
    let mut l = 0;
    let mut h = x;
    while h - l > 1 {
        let m = (l + h) / 2 as i32;
        if x / m < m {
            h = m;
        } else {
            l = m;
        }
    }
    l
}

#[cfg(test)]
mod test {
    use crate::leetcode::my_sqrt_69::my_sqrt;

    #[test]
    fn test() {
        let a = my_sqrt(1);
        assert_eq!(1, a)
    }
}
